package org.example.myleet.p590;

import org.example.myleet.model.Node;

import java.util.*;

public class Solution {

    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (null == root) {
            return result;
        }
        Deque<Node> queue = new LinkedList<>();
        queue.push(root);
        while (!queue.isEmpty()) {
            Node node = queue.pop();
            if (null == node.children || 1 > node.children.size()) {
                result.add(node.val);
            } else {
                queue.push(node);
                int size = node.children.size();
                for (int i = 1; i <= size; ++i) {
                    Node child = node.children.remove(size - i);
                    queue.push(child);
                }
            }
        }
        return result;
    }

//    public List<Integer> postorder(Node root) {
//        List<Integer> result = new ArrayList<>();
//        if (null == root) {
//            return result;
//        }
//        Deque<Object> queue = new LinkedList<>();
//        queue.push(root);
//        while (!queue.isEmpty()) {
//            Object obj = queue.pop();
//            if (obj instanceof Integer) {
//                result.add((Integer) obj);
//            } else {
//                Node node = (Node) obj;
//                queue.push(node.val);
//                for (int i = node.children.size() - 1; i >= 0; --i) {
//                    Node child = node.children.get(i);
//                    if (null == child.children || 1 > child.children.size()) {
//                        queue.push(child.val);
//                    } else {
//                        queue.push(child);
//                    }
//                }
//            }
//        }
//        return result;
//    }

//    public List<Integer> postorder(Node root) {
//        List<Integer> result = new ArrayList<>();
//        if (null == root) {
//            return result;
//        }
//        Deque<Node> queue = new LinkedList<>();
//        queue.push(root);
//        while (!queue.isEmpty()) {
//            Node node = queue.pop();
//            if (null == node.children || 1 > node.children.size()) {
//                result.add(node.val);
//            } else {
//                queue.push(new Node(node.val));
//                for (int i = node.children.size() - 1; i >= 0; --i) {
//                    queue.push(node.children.get(i));
//                }
//            }
//        }
//        return result;
//    }
}
